/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Gramatica;

import PL3.Token;
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;

/**
 *
 * @author David Fernandez <david@gluem.org>
 */
public class LL1Factory {

    private static HashMap<SimboloNoTerminal, HashSet<SimboloTerminal>> primeros = new HashMap<SimboloNoTerminal, HashSet<SimboloTerminal>>();

    ;
    private static HashMap<SimboloNoTerminal, HashSet<SimboloTerminal>> siguientes = new HashMap<SimboloNoTerminal, HashSet<SimboloTerminal>>();
    public static final SimboloTerminal finDeCadena = new SimboloTerminal('$');
    private static HashMap<SimboloNoTerminal, Boolean> calculadosPrimeros = new HashMap<SimboloNoTerminal, Boolean>();
    private static HashMap<SimboloNoTerminal, Boolean> calculadosSiguientes = new HashMap<SimboloNoTerminal, Boolean>();

    private static void generarPrimeros(GIC g) {


        HashSet<SimboloNoTerminal> noTerminales = g.getNoTerminales();

        Iterator it = noTerminales.iterator();

        while (it.hasNext()) {

            SimboloNoTerminal s = (SimboloNoTerminal) it.next();

            primeros.put(s, new HashSet<SimboloTerminal>());
            calculadosPrimeros.put(s, Boolean.FALSE);
        }

        it = noTerminales.iterator();

        while (it.hasNext()) {

            SimboloNoTerminal s = (SimboloNoTerminal) it.next();

            if (calculadosPrimeros.get(s) == Boolean.FALSE) {

                primeroDeNoTerminal(g, s);
            }
        }



    }

    private static void primeroDeNoTerminal(GIC g, SimboloNoTerminal s) {

        HashSet<SimboloTerminal> primero = new HashSet<SimboloTerminal>();
        Produccion p = g.getProducciones().get(s);

        Iterator it = p.getParteDerecha().iterator();

        while (it.hasNext()) {

            ArrayList<ISimbolo> aux = (ArrayList<ISimbolo>) it.next();

            HashSet<SimboloTerminal> primeroAux = primeroDeExpresion(g, aux);

            primero.addAll(primeroAux);

        }

        calculadosPrimeros.remove(s);
        calculadosPrimeros.put(s, Boolean.TRUE);

        primeros.remove(s);
        primeros.put(s, primero);


    }

    private static HashSet<SimboloTerminal> primeroDeExpresion(GIC g, ArrayList<ISimbolo> exp) {

        HashSet<SimboloTerminal> primero = new HashSet<SimboloTerminal>();

        if (!exp.isEmpty()) {

            //ES LAMBDA
            if (exp.get(0).getClass().getName().equals("Gramatica.SimboloTerminal")
                    && exp.get(0).equals(GIC.lambda)) {

                primero.add(GIC.lambda);


                //ES TERMINAL
            } else if (exp.get(0).getClass().getName().equals("Gramatica.SimboloTerminal")
                    && g.getTerminales().contains((SimboloTerminal) exp.get(0))) {

                primero.add((SimboloTerminal) exp.get(0));


                //ES NO TERMINAL
            } else if (exp.get(0).getClass().getName().equals("Gramatica.SimboloNoTerminal")
                    && g.getNoTerminales().contains((SimboloNoTerminal) exp.get(0))) {

                if (calculadosPrimeros.get((SimboloNoTerminal) exp.get(0)) == Boolean.FALSE) {

                    primeroDeNoTerminal(g, (SimboloNoTerminal) exp.get(0));

                }

                HashSet<SimboloTerminal> primerosAux = primeros.get((SimboloNoTerminal) exp.get(0));
                //System.out.println("Primero de: " + exp.get(0) + " es " + primerosAux);

                primero.addAll(primerosAux);

                /*  Iterator it = primerosAux.iterator();

                while (it.hasNext()) {

                SimboloTerminal aux = (SimboloTerminal) it.next();

                primero.add(aux);


                }*/

                if (primeros.get((SimboloNoTerminal) exp.get(0)).contains(GIC.lambda)) {

                    HashSet<SimboloTerminal> primeroAux2;

                    primeroAux2 = primeroDeExpresion(g, new ArrayList(exp.subList(1, exp.size())));


                    primero.addAll(primeroAux2);
                    /*Iterator it2 = primeroAux2.iterator();

                    while (it2.hasNext()){

                    SimboloTerminal aux2 = (SimboloTerminal) it2.next();
                    primero.add(aux2);
                    }*/
                }



            }

        } else {
            return new HashSet<SimboloTerminal>();
        }


        return primero;

    }

    private static void generarSiguientes(GIC g) {



        Iterator it = g.getNoTerminales().iterator();

        while (it.hasNext()) {

            SimboloNoTerminal s = (SimboloNoTerminal) it.next();

            siguientes.put(s, new HashSet<SimboloTerminal>());
            calculadosSiguientes.put(s, Boolean.FALSE);
        }

        it = g.getNoTerminales().iterator();

        while (it.hasNext()) {

            SimboloNoTerminal simbolo = (SimboloNoTerminal) it.next();

            if (calculadosSiguientes.get(simbolo) == Boolean.FALSE) {

                siguienteDeNoTerminal(g, simbolo);
            }
        }




    }

    private static void siguienteDeNoTerminal(GIC g, SimboloNoTerminal s) {

        // System.out.println(s);

        HashSet<SimboloTerminal> siguiente = new HashSet<SimboloTerminal>();

        if (g.getInicial().equals(s)) {

            siguiente.add(finDeCadena);
        }

        Iterator it = g.getNoTerminales().iterator();

        while (it.hasNext()) {

            SimboloNoTerminal aux = (SimboloNoTerminal) it.next();

            Produccion pAux = g.getProducciones().get(aux);

            Iterator it2 = pAux.getParteDerecha().iterator();

            while (it2.hasNext()) {

                ArrayList<ISimbolo> pDer = (ArrayList<ISimbolo>) it2.next();

                int index = pDer.indexOf(s);

                if (index != -1) {

                    //Si esta el simbolo que queremos
                    if (index < pDer.size() - 1) { //Si no esta al final
                        ArrayList<ISimbolo> expresionAux = new ArrayList<ISimbolo>(pDer.subList(index + 1, pDer.size()));
                        HashSet<SimboloTerminal> sig = primeroDeExpresion(g, expresionAux);
                        //System.out.println("SIGUIENTE: " + sig);
                        siguiente.addAll(sig);

                        if (siguiente.contains(GIC.lambda)) {

                            siguiente.remove(GIC.lambda);

                            if (!pAux.getParteIzquierda().equals(s)) {

                                if (calculadosSiguientes.get(pAux.getParteIzquierda()) == Boolean.FALSE) {

                                    siguienteDeNoTerminal(g, pAux.getParteIzquierda());
                                }
                                siguiente.addAll(siguientes.get(pAux.getParteIzquierda()));


                            }
                        }

                    } else { //Si esta al final

                        if (!pAux.getParteIzquierda().equals(s)) {
                            if (calculadosSiguientes.get(pAux.getParteIzquierda()) == Boolean.FALSE) {

                                siguienteDeNoTerminal(g, pAux.getParteIzquierda());
                            }

                            siguiente.addAll(siguientes.get(pAux.getParteIzquierda()));
                        }
                    }
                }
            }



        }
        siguientes.remove(s);
        siguientes.put(s, siguiente);
        calculadosSiguientes.remove(s);
        calculadosSiguientes.put(s, Boolean.TRUE);

        //System.out.println("Siguientes de " + s + " son " + siguientes.get(s));
    }

    private static boolean esLL1(GIC g) {

        boolean correcto = true;
        boolean contieneLambda = false;

        Enumeration en = g.getProducciones().elements();

        while (en.hasMoreElements() && correcto) {

            //Para cada produccion
            Produccion p = (Produccion) en.nextElement();

            //Si tienes mas de un elemento
            if (p.getParteDerecha().size() > 1) {

                Iterator it1 = p.getParteDerecha().iterator();


                while (it1.hasNext() && correcto) { //Comprueba que la interseccion de todas las partes dchas. tomadas de 2en2 sea vacia.

                    ArrayList<ISimbolo> aux1 = (ArrayList<ISimbolo>) it1.next();

                    //Comprobamos que contenga Lambda para luego
                    if (aux1.get(0).equals(GIC.lambda)) {

                        contieneLambda = true;
                    }

                    Iterator it2 = p.getParteDerecha().iterator();

                    while (it2.hasNext() && !it2.next().equals(aux1)); //Nos saltamos los ya comprobados y si son iguales

                    while (it2.hasNext() && correcto) {

                        ArrayList<ISimbolo> aux12 = new ArrayList<ISimbolo>(aux1);
                        ArrayList<ISimbolo> aux2 = (ArrayList<ISimbolo>) it2.next();

                        aux12.retainAll(aux2);

                        correcto = aux12.isEmpty();

                    }



                }

                if (contieneLambda) {

                    Iterator it = p.getParteDerecha().iterator();

                    //Tenemos que comprobar que la interseccion de prim(cada una de las partes derechas) con siguiente
                    //del simbolo que estamos mirando sea vacia.

                    while (it.hasNext() && correcto) {

                        ArrayList<ISimbolo> pDer = (ArrayList<ISimbolo>) it.next();

                        if (!pDer.get(0).equals(GIC.lambda)) {

                            HashSet<SimboloTerminal> prim = primeroDeExpresion(g, pDer);
                            //System.out.println(siguientes);
                            HashSet<SimboloTerminal> sig = new HashSet<SimboloTerminal>(siguientes.get(p.getParteIzquierda()));

                            prim.retainAll(sig);

                            correcto = prim.isEmpty();
                        }

                    }

                }



            }






        }
        return correcto;
    }

    public static HashMap<String, HashMap<String, ArrayList<ISimbolo>>> generarTablaAnalisisSintactico(GIC g) {

        HashMap<String, HashMap<String, ArrayList<ISimbolo>>> tabla = new HashMap<String, HashMap<String, ArrayList<ISimbolo>>>();

        generarPrimeros(g);
        generarSiguientes(g);

        if (esLL1(g)) {

            Enumeration en = g.getProducciones().elements();

            while (en.hasMoreElements()) {

                Produccion p = (Produccion) en.nextElement();

                SimboloNoTerminal izda = p.getParteIzquierda();

                tabla.put(izda.getSimbolo(), new HashMap<String, ArrayList<ISimbolo>>());

                Iterator it = p.getParteDerecha().iterator();

                while (it.hasNext()) {


                    ArrayList<ISimbolo> pDer = (ArrayList<ISimbolo>) it.next();

                    if (!pDer.get(0).equals(GIC.lambda)) {

                        HashSet<SimboloTerminal> prim = primeroDeExpresion(g, pDer);

                        Iterator it2 = prim.iterator();

                        while (it2.hasNext()) {
                            SimboloTerminal simbolo = (SimboloTerminal) it2.next();

                            tabla.get(izda.getSimbolo()).put(simbolo.getSimbolo(), new ArrayList<ISimbolo>(pDer));
                        }
                    } else {

                        Iterator it2 = siguientes.get(izda).iterator();

                        while (it2.hasNext()) {

                            SimboloTerminal simbolo = (SimboloTerminal) it2.next();

                            tabla.get(izda.getSimbolo()).put(simbolo.getSimbolo(), new ArrayList<ISimbolo>(pDer));
                        }
                    }



                }


            }


        } else {

            tabla = null;
        }





        return tabla;
    }

    public static void main(String[] args) {

        SimboloNoTerminal e = new SimboloNoTerminal("E");
        SimboloNoTerminal rt = new SimboloNoTerminal("RT");
        SimboloNoTerminal t = new SimboloNoTerminal("T");
        SimboloNoTerminal rf = new SimboloNoTerminal("RF");
        SimboloNoTerminal f = new SimboloNoTerminal("F");

        SimboloTerminal mas = new SimboloTerminal('+');
        SimboloTerminal por = new SimboloTerminal('*');
        SimboloTerminal id = new SimboloTerminal("id");
        SimboloTerminal num = new SimboloTerminal("num");
        SimboloTerminal pA = new SimboloTerminal('(');
        SimboloTerminal pC = new SimboloTerminal(')');


        ArrayList<ISimbolo> p1 = new ArrayList<ISimbolo>();
        ArrayList<ISimbolo> p2 = new ArrayList<ISimbolo>();
        ArrayList<ISimbolo> p3 = new ArrayList<ISimbolo>();

        p1.add(t);
        p1.add(rt);

        ArrayList<ArrayList<ISimbolo>> pDer = new ArrayList<ArrayList<ISimbolo>>();

        pDer.add(p1);



        //E
        Produccion prodE = new Produccion(e, pDer);


        p1 = new ArrayList<ISimbolo>();

        p1.add(mas);
        p1.add(t);
        p1.add(rt);


        p2.add(GIC.lambda);

        pDer = new ArrayList<ArrayList<ISimbolo>>();

        pDer.add(p1);
        pDer.add(p2);

        Produccion prodRT = new Produccion(rt, pDer);


        p1 = new ArrayList<ISimbolo>();
        p2 = new ArrayList<ISimbolo>();
        pDer = new ArrayList<ArrayList<ISimbolo>>();

        p1.add(f);
        p1.add(rf);



        pDer.add(p1);
        //pDer.add(p2);

        Produccion prodT = new Produccion(t, pDer);



        p1 = new ArrayList<ISimbolo>();
        p2 = new ArrayList<ISimbolo>();
        pDer = new ArrayList<ArrayList<ISimbolo>>();

        p1.add(por);
        p1.add(f);
        p1.add(rf);

        p2.add(GIC.lambda);

        p3.add(por);
        //p3.add(e);
        //p3.add(mas);

        pDer.add(p1);
        pDer.add(p2);
        //pDer.add(p3);


        Produccion prodRF = new Produccion(rf, pDer);

        p1 = new ArrayList<ISimbolo>();
        p2 = new ArrayList<ISimbolo>();
        p3 = new ArrayList<ISimbolo>();

        pDer = new ArrayList<ArrayList<ISimbolo>>();

        p1.add(id);
        p2.add(num);
        p3.add(pA);
        p3.add(e);
        p3.add(pC);


        pDer.add(p1);
        pDer.add(p2);
        pDer.add(p3);


        Produccion prodF = new Produccion(f, pDer);


        GIC g = new GIC();

        HashSet<SimboloTerminal> terminales = new HashSet<SimboloTerminal>();
        HashSet<SimboloNoTerminal> noTerminales = new HashSet<SimboloNoTerminal>();
        Hashtable<SimboloNoTerminal, Produccion> producciones = new Hashtable<SimboloNoTerminal, Produccion>();

        terminales.add(mas);
        terminales.add(por);
        terminales.add(id);
        terminales.add(num);
        terminales.add(pA);
        terminales.add(pC);

        noTerminales.add(e);
        noTerminales.add(rt);
        noTerminales.add(t);
        noTerminales.add(rf);
        noTerminales.add(f);

        producciones.put(e, prodE);
        producciones.put(rt, prodRT);
        producciones.put(t, prodT);
        producciones.put(rf, prodRF);
        producciones.put(f, prodF);


        g.setInicial(e);
        g.setTerminales(terminales);
        g.setNoTerminales(noTerminales);
        g.setProducciones(producciones);

        //System.out.println(g);

       // System.out.println(generarTablaAnalisisSintactico(g));


        Token t0 = new Token("(");
        Token t1 = new Token("id");
        Token t2 = new Token("+");
        Token t3 = new Token("num");
        Token t4 = new Token("*");
        Token t5 = new Token("num");
        Token t6 = new Token("+");
        Token t7 = new Token("id");
        Token t8 = new Token("$");
        Token t9 = new Token(")");

        ArrayList<Token> entrada = new ArrayList<Token>();

        entrada.add(t0);
        entrada.add(t1);
        entrada.add(t2);
        entrada.add(t3);
        entrada.add(t9);
        entrada.add(t4);
        entrada.add(t5);
        entrada.add(t6);
        entrada.add(t7);
        entrada.add(t8);

        System.out.println(g.pertenece(entrada));







    }
}
